package 剑指offer.树;

/**
 * 请实现一个函数，用来判断一颗二叉树是不是对称的。
 * 注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
 */
public class 第28题对称的二叉树 {

    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    /*
    一颗树是对称的表明它的 DLR == DRL

    可以遍历两次拿到 DLR 和 DRL 比较他们是否一致

    也可以复制一份树，分两种方式一边遍历一遍比对，一旦发现不一致的数据立刻返回
     */
    boolean isSymmetrical(TreeNode pRoot) {
        // 应该问一下面试官，null 的 pRoot 是否为对称的

        // 本题的测试用例 null 的 pRoot 就是对称的

        return compare(pRoot, pRoot);
    }

    private boolean compare(TreeNode pRoot, TreeNode pRoot1) {
        if (pRoot == null && pRoot1 == null)
            return true;
        if (pRoot == null || pRoot1 == null)
            return false;
        if (pRoot.val != pRoot1.val)
            return false;
        return compare(pRoot.left, pRoot1.right) && compare(pRoot.right, pRoot1.left);
    }
}
